import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
//        Solution solution = new Solution();
//        System.out.println(solution.mergeKLists());
    }
}


class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

//题解方法，用优先队列，保存所有列表头元素，每次取最小
class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = new ListNode();
        ListNode tail = ans;

        Queue<ListNode> queue = new PriorityQueue<>((o1, o2) -> {
            if(o1.val > o2.val) return 1;
            if(o1.val < o2.val) return -1;
            return 0;
        });
        for(ListNode list: lists){
            if(list != null) queue.add(list);
        }

        ListNode min = queue.poll();
        while(min != null){
            tail.next = min;
            tail = tail.next;
            if(min.next != null) queue.add(min.next);
            min = queue.poll();
        }
        tail.next = null;
        return ans.next;
    }
}


//题解方法，递归两两排序
class Solution1 {

    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r){
        if (l > r) return null;
        if (l == r) return lists[l];
        int mid = (l + r) / 2;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }


    public ListNode mergeTwoLists(ListNode list1, ListNode list2){
        if(list1 == null || list2 == null){
            return list1 == null ? list2 : list1;
        }

        ListNode res = new ListNode();
        ListNode tail = res;
        ListNode node1 = list1, node2 = list2;
        while(node1 != null && node2 != null){
            if(node1.val <= node2.val){
                tail.next = node1;
                node1 = node1.next;
            }
            else{
                tail.next = node2;
                node2 = node2.next;
            }
            tail = tail.next;
        }
        tail.next = node1 == null ? node2 : node1;
        return res.next;
    }
}


//每次找出所有列表头元素的最小值加入结果列表
class Solution2 {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = new ListNode();
        ListNode tail = ans;

        int min = pollMin(lists);
        while(min != Integer.MAX_VALUE){
            tail.next = new ListNode(min);
            tail = tail.next;
            min = pollMin(lists);
        }
        return ans.next;
    }

    private int pollMin(ListNode[] lists) {
        int min = Integer.MAX_VALUE;
        int minIdx = -1;
        for(int i = 0; i < lists.length; i++){
            if(lists[i] != null && lists[i].val < min){
                min = lists[i].val;
                minIdx = i;
            }
        }
        if(minIdx != -1){
            lists[minIdx] = lists[minIdx].next;
        }
        return min;
    }
}